package com.review.dp;

public class LC_53 {
    public static int maxSubArray(int[] nums) {
        int max = nums[0];
        int length = nums.length;
        int sum = nums[0];
        for (int i = 1; i < length; i++) {
            if (sum >= 0) {
                max = Math.max(max, sum);
                max = Math.max(max, sum + nums[i]);
                sum += nums[i];
            } else {
                while (i < length && nums[i] < 0) {
                    max = Math.max(max, nums[i]);
                    i++;
                }
                if (i < length) {
                    sum = nums[i];
                }
            }
            max = Math.max(max, sum);
        }
        return max;
    }

    public static int maxSubArray_2(int[] nums) {
        int max = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            nums[i] = Math.max(nums[i], nums[i - 1] + nums[i]);
            max = Math.max(nums[i], max);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {1};
        System.out.println(maxSubArray(nums));
        System.out.println(maxSubArray_2(nums));
    }
}
